package _11_整理题目._7_查找排序._1_排序算法;

import org.junit.Test;

import java.util.Arrays;

/**
 * 思路：分治
 * 每次找一个基准值（取左边第一个），
 * 将所有大于基准值的数移动到基准值的右边，
 * 将所有小于基准值的数移动到基准值的左边，
 * 即完成一次快排。
 * 根据基准值将数组分为两组，再递归的对左右两边重复上面操作
 * 
 * 评价：
 * 由于移动数据时采用了比冒泡排序更快的方法，所以可以看做是对其的优化
 * 
 * 实现：（如何更快的将数据移动到基准值的两侧）
 * 双指针，i,j分别从数组的两侧开始交替移动，直至相遇
 */
public class _02_快速排序 {
    
    private void quickSort(int[] arr, int left, int right) {
        if(left < right) {
            int key = arr[left];
            int i = left, j = right;
            while(i < j) {
                // j-- 从右边
                while(i < j && arr[j] > key) {
                    j--;
                }
                if(i < j) {
                    swap(arr, i, j);
                    i++;
                }
                
                // i++ 从左边
                while(i < j && arr[i] < key) {
                    i++;
                }
                if(i < j) {
                    swap(arr, i, j);
                    j--;
                }
            }
            arr[i] = key;
            quickSort(arr, left, i-1);// 递归左边
            quickSort(arr, i+1, right);// 递归右边
        }
    }
    
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    @Test
    public void main() {
        int[] input = {1332802,1177178,1514891,871248,753214,123866,1615405,328656,1540395,968891,1884022,252932,1034406,1455178,821713,486232,860175,1896237,852300,566715,1285209,1845742,883142,259266,520911,1844960,218188,1528217,332380,261485,1111670,16920,1249664,1199799,1959818,1546744,1904944,51047,1176397,190970,48715,349690,673887,1648782,1010556,1165786,937247,986578,798663};
        System.out.println(Arrays.toString(input));
        quickSort(input, 0, input.length-1);
        System.out.println(Arrays.toString(input));
        System.out.println(input[24-1]);
    }
}
